前言

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
那就開始今天的解題吧~

Question

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Constraints:

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

Think

給一個氣溫的陣列，回傳一個陣列，紀錄每天的氣溫要過幾天才會上升超過當天的溫度~

Monotonic Stack is a stack whose elements are monotonically increasing or decreasing. It contains all qualities that a typical stack has and its elements are all monotonic decreasing or increasing.

這邊可以用Monotonic Stack來做，時間複雜度可以降為O(n)。

• 首先，如果我們的stack是空的或是我們現在的這個溫度大於stack中最後放進去的溫度，就把stack最後的值pop出來，因為這個值已經找到最近的然後又比他大的溫度了。
  • 然後index減掉stack pop出來的stack_index後，再存回要回傳的result list。
• 一直到stack空或是現在的溫度小於stack中的最後放進去的溫度，就直接把現在的溫度push進去。

Code

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # [{"index": val1, "temp": val2}, ...}]
        stack = []
        result = [0 for x in range(len(temperatures))]
        
        for index, temp in enumerate(temperatures):
            while stack and temp > stack[-1]["temp"]:
                #print("Stack pop lastest: \n", stack)
                last_element = stack.pop()
                stack_index, stack_temp = last_element["index"], last_element["temp"]
                
                result[stack_index] = index - stack_index
                #print("Result add: \n", result)
            stack.append({"index": index, "temp": temp})
            #print("Stack append: \n", stack, "\n----------\n")
            
        # print("Result: ", result)
        
        return result

• 解法2

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        result = [0]*len(temperatures)
        
        for index, temp in enumerate(temperatures):
            while stack and temp > temperatures[stack[-1]]:
                stack_index = stack.pop()
                
                result[stack_index] = index - stack_index
            stack.append(index)
        
        return result

Submission

• 第一個Code，本來用手機寫的時候，有Success，程式碼複製到電腦跑結果變成Time Limit Exceeded:<

• 只好修改一下解法了~
  

今天就到這邊啦~
大家明天見